package 优先算法.双指针.有效三角形的个数;

import java.util.Arrays;

/**
 * @author <a href="https://leetcod e.cn/problems/valid-triangle-number/"
 */
public class RelTriangle {
    public static void main(String[] args) {
        Solution so = new Solution();
        int[] nums = {2,2,3,10};
        System.out.println(so.triangleNumber(nums));
    }
}
class Solution {
    public int triangleNumber(int[] nums) {
        //升序数组
        Arrays.sort(nums);

        int sum=0;
        int left=0,right;

        for(int i=nums.length-1; i>=2; i--){
            right=i-1;
            sum+=SearchNum(nums,left,right,i);
        }
        return sum;
    }
    public static int SearchNum(int[] nums,int left,int right, int i){
        int sum=0;
        int Max =nums[i];
        while(left<right){
            if(nums[left]+nums[right]>Max){
                sum+=right-left;
                right--;
            }else{
                //如果两个最大值都不行的话，这组最大值就没有了
                if(left==right-1 || nums[right-1]+nums[right]<Max){
                    break;
                }
                left++;
            }
        }
        return sum;
    }
}
